// -*- mode: C++ ; compile-command: "g++ -I.. -g -O2 -c index.cc" -*-
/*
 *  Copyright (C) 2000,7 B. Parisse, Institut Fourier, 38402 St Martin d'Heres
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

#include "config.h"
#include "first.h"
#include "libs/gmpwrap.h"
#include "index.h"
#include "basics.h"
#include <cmath>
#include <stdio.h>
#include <stdexcept>
#include <cassert>

CASPP_NS_BEGIN

Degree_v index_gcd(const Degree_v & a,const Degree_v & b) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end(),itb=b.begin();
    unsigned s=itaend-ita;
    Degree_v res(s);
    Degree_v::iterator itres=res.begin();
    CASPP_DEBUG_TEST((s!=b.size()),"Error index.cc index_gcd");
    for (;ita!=itaend;++itb,++itres,++ita)
        *itres=min(*ita,*itb);
    return res;
}

Degree_v index_lcm(const Degree_v & a,const Degree_v & b) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end(),itb=b.begin();
    unsigned s=itaend-ita;
    Degree_v res(s);
    Degree_v::iterator itres=res.begin();
    CASPP_DEBUG_TEST((s!=b.size()),"index.cc index_lcm");
    for (;ita!=itaend;++itb,++itres,++ita)
        *itres=max(*ita,*itb);
    return res;
}

void index_lcm(const Index & a,const Index & b,Degree_v & res) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end(),itb=b.begin();
    unsigned s=itaend-ita;
    res.resize(s);
    Degree_v::iterator itres=res.begin();
    for (;ita!=itaend;++itb,++itres,++ita)
        *itres=max(*ita,*itb);
}

// index and t_Monomial ordering/operations implementation

Degree_v operator + (const Degree_v & a, const Degree_v & b) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end(),itb=b.begin();
    unsigned s=itaend-ita;
    Degree_v res(s);
    Degree_v::iterator itres=res.begin();
    CASPP_DEBUG_TEST((s!=b.size()),"index.cc operator +");
    for (;ita!=itaend;++itb,++itres,++ita)
        *itres=(*ita)+(*itb);
    return res;
}

Degree_v operator - (const Degree_v & a, const Degree_v & b) {
    Degree_v res;
    Degree_v::const_iterator ita=a.begin(),itaend=a.end(),itb=b.begin();
    unsigned s=itaend-ita;
    CASPP_DEBUG_TEST((s!=b.size()),"index.cc operator -");
    res.reserve(s);
    for (;ita!=itaend;++ita,++itb)
        res.push_back((*ita)-(*itb));
    return res;
}

Degree_v operator | (const Degree_v & a, const Degree_v & b) {
    Degree_v res;
    Degree_v::const_iterator ita=a.begin(),itaend=a.end(),itb=b.begin();
    unsigned s=itaend-ita;
    CASPP_DEBUG_TEST((s!=b.size()),"index.cc operator |");
    res.reserve(s);
    for (;ita!=itaend;++ita,++itb)
        res.push_back((*ita) | (*itb));
    return res;
}

Degree_v operator - (const Degree_v & a) {
    Degree_v res;
    Degree_v::const_iterator ita=a.begin(),itaend=a.end();
    int s=itaend-ita;
    res.reserve(s);
    for (;ita!=itaend;++ita)
        res.push_back(-(*ita));
    return res;
}

Degree_v operator * (const Degree_v & a, int fois) {
    Degree_v res;
    Degree_v::const_iterator ita=a.begin(),itaend=a.end();
    res.reserve(itaend-ita);
    for (;ita!=itaend;++ita)
        res.push_back((*ita)*fois);
    return res;
}

Degree_v operator / (const Degree_v & a, int divisepar) {
    Degree_v res;
    Degree_v::const_iterator ita=a.begin(),itaend=a.end();
    res.reserve(itaend-ita);
    for (;ita!=itaend;++ita)
        res.push_back((*ita)/divisepar);
    return res;
}

int operator / (const Degree_v & a, const Degree_v & b) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end(),itb=b.begin(),itbend=b.end();
    CASPP_DEBUG_TEST((itaend-ita!=signed(b.size())),"index.cc operator /");
    for (;ita!=itaend;++ita,++itb) {
        if (*itb)
            return *ita / *itb;
    }
    return 0;
}

bool all_sup_equal (const Degree_v & a, const Degree_v & b) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end(),itb=b.begin();
    CASPP_DEBUG_TEST((itaend-ita!=signed(b.size())),"index.cc operator >=");
    for (;ita!=itaend;++ita,++itb) {
        if ((*ita)<(*itb))
            return false;
    }
    return true;
}

bool all_inf_equal (const Degree_v & a, const Degree_v & b) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end(),itb=b.begin();
    CASPP_DEBUG_TEST((itaend-ita!=signed(b.size())),"index.cc operator <=");
    for (;ita!=itaend;++ita,++itb) {
        if ((*ita)>(*itb))
            return false;
    }
    return true;
}

std::string print_INT_(int i) {
    char c[256];
    my_sprintf(c,"%d",i);
    return c;
}

std::string hexa_print_INT_(int i) {
    char c[256];
    my_sprintf(c,"%X",i);
    return std::string("0x")+c;
}

std::string octal_print_INT_(int i) {
    char c[256];
    my_sprintf(c,"%o",i);
    return std::string("0o")+c;
}

std::string binary_print_INT_(int i) {
    char c[256];
    mpz_t tmp;
    mpz_init_set_ui(tmp, i);
    mpz_get_str(c, 2, tmp);
    mpz_clear(tmp);
    return std::string("0b")+c;
}

/*
  std::string print_INT_(int i) {
    if (!i)
      return std::string("0");
    if (i<0)
      return std::string("-")+print_INT_(-i);
    int length = (int) std::floor(std::log10((double_t) i));
    char s[length+2];
    s[length+1]=0;
    for (;length>-1;--length,i/=10)
      s[length]=i%10+'0';
    return s;
  }
  */

std::string print_INT_(const std::vector<short int> & m) {
    std::vector<short int>::const_iterator it=m.begin(),itend=m.end();
    if (it==itend)
        return "";
    std::string s("[");
    for (;;) {
        s += print_INT_(*it);
        ++it;
        if (it==itend) {
            s +=']';
            return s;
        } else {
            s += ',';
        }
    }
}

std::string print_INT_(const int_v & m) {
    int_v::const_iterator it=m.begin(),itend=m.end();
    if (it==itend)
        return "";
    std::string s("[");
    for (;;) {
        s += print_INT_(*it);
        ++it;
        if (it==itend)
            return s+']';
        else
            s += ',';
    }
}

CASPP_OSTREAM_OUT & operator << (CASPP_OSTREAM_IN & os, const Degree_v & m ) {
    return os << ":Degree_v: " << print_INT_(m) << " " ;
}

void dbgprint(const Degree_v & i) {
    COUT << i << std::endl;
}

Degree_v mergeindex(const Degree_v & i,const Degree_v & j) {
    Degree_v res(i);
    Degree_v::const_iterator it=j.begin(),itend=j.end();
    res.reserve(i.size()+(itend-it));
    for (;it!=itend;++it)
        res.push_back(*it);
    return res;
}

// by convention 0 -> 0 for permutations beginning at index 1
int_v inverse(const int_v & p) {
    int_v inv(p);
    int n=p.size();
    for (int i=0;i<n;i++) {
        inv[p[i]]=i; // that's the definition of inv!!
    }
    return inv;
}

// transposition
int_v transposition(int i,int j,int size) {
    if (i>j)
        return transposition(j,i,size);
    int_v t;
    for (int k=0;k<i;k++)
        t.push_back(k);
    t.push_back(j);
    for (int k=i+1;k<j;k++)
        t.push_back(k);
    t.push_back(i);
    for (int k=j+1;k<size;k++)
        t.push_back(k);
    return t;
}

bool has(const Degree_v & p,int r) {
    Degree_v::const_iterator it=p.begin(),itend=p.end();
    for (;it!=itend;++it) {
        if (*it==r)
            return true;
    }
    return false;
}

bool is_zero(const Degree_v & p) {
    Degree_v::const_iterator it=p.begin(),itend=p.end();
    for (;it!=itend;++it) {
        if (*it)
            return false;
    }
    return true;
}

#if defined(CASPP_NO_OPTIMIZATIONS) || ((defined(VISUALC) || defined(__APPLE__)) && !defined(CASPP_VECTOR))
bool operator == (const Index & i1, const Index & i2) {
    if (i1.r_p==i2.r_p)
        return true;
    return (i1.r_p->i==i2.r_p->i);
}
#else
Degree_v Index::iref() const {
    if ( (taille % 2)==0)
        return r_p->i;
    return Degree_v(direct,direct+taille/2);
}

Degree_v::iterator Index::begin() {
    if ( (taille % 2)==0)
        return r_p->i.begin();
    return Degree_v::iterator((caspp::Degree *) direct);
}

Degree_v::iterator Index::end() {
    if ( (taille % 2)==0)
        return r_p->i.end();
    return Degree_v::iterator((caspp::Degree *) direct + taille/2) ;
}

Degree_v::const_iterator Index::begin() const {
    if ( (taille % 2)==0)
        return r_p->i.begin();
    return Degree_v::const_iterator((caspp::Degree *) direct);
}

Degree_v::const_iterator Index::end() const {
    if ( (taille % 2)==0)
        return r_p->i.end();
    return Degree_v::const_iterator((caspp::Degree *) direct + taille/2 );
}

void Index::clear() {
    if ( (taille % 2)==0)
        r_p->i.clear();
    else
        taille=1;
}

void Index::reserve(size_t n) {
    if (int(n)>POLY_VARS) {
        if ( taille % 2)
            // alloc a true std::vector with correct size, copy into
            r_p = new DegreesRef(begin(),end());
        // taille=0;
        r_p->i.reserve(n);
    }
}

void Index::push_back(Degree x) {
    if ( taille % 2) {
        int pos = taille /2 ;
        taille += 2;
        if (pos<POLY_VARS) {
            direct[pos]=x;
            return;
        }
        r_p = new DegreesRef(Degree_v::iterator((caspp::Degree *)direct),Degree_v::iterator((caspp::Degree *)direct+pos));
        // taille = 0;
    }
    r_p->i.push_back(x);
}

size_t Index::size() const {
    if (taille % 2)
        return taille/2;
    else
        return r_p->i.size();
}

Index Index::set_first_zero() const {
    if ( (taille % 2) == 0) {
        Degree_v i(r_p->i);
        assert(i.size());
        i[0]=0;
        return Index(i);
    }
    Index copie(*this);
    copie.direct[0]=0;
    return copie;
}

bool operator == (const Index & i1, const Index & i2) {
    if (((i1.taille % 2))==0) {
        if (i1.r_p==i2.r_p)
            return true;
        return (i1.r_p->i==i2.r_p->i);
    }
    if (i1.taille!=i2.taille)
        return false;
    const Degree * i_p=i1.direct, *i1end=i_p+i1.taille/2,* i_p=i2.direct;
    for (;i_p!=i1end;++i_p,++i_p) {
        if (*i_p!=*i_p)
            return false;
    }
    return true;
}

#endif // VISUALC

bool Index::is_zero() const {
    Degree_v::const_iterator it=begin(),itend=end();
    for (;it!=itend;++it) {
        if (*it)
            return false;
    }
    return true;
}

size_t Index::total_degree() const {
    size_t i=0;
    for (Degree_v::const_iterator it=begin();it!=end();++it)
        i=i+(*it);
    return i;
}


Index operator + (const Index & a, const Index & b) {
    Degree_v::const_iterator ita=a.begin();
    Degree_v::const_iterator itaend=a.end();
    Degree_v::const_iterator itb=b.begin();
    int s=itaend-ita;
#ifdef CASPP_DEBUG_SUPPORT
    if (s!=signed(b.size()))
        setsizeerr(gettext("index.cc Index operator +"));
#endif // CASPP_DEBUG_SUPPORT
    Index res(s);
    Degree_v::iterator it=res.begin();
    for (;ita!=itaend;++it,++itb,++ita)
        *it = (*ita)+(*itb);
    return res;
}

Index operator - (const Index & a, const Index & b) {
    Degree_v::const_iterator ita=a.begin();
    Degree_v::const_iterator itaend=a.end();
    Degree_v::const_iterator itb=b.begin();
    int s=itaend-ita;
#ifdef CASPP_DEBUG_SUPPORT
    if (s!=signed(b.size()))
        setsizeerr(gettext("index.cc Index operator -"));
#endif // CASPP_DEBUG_SUPPORT
    Index res(s);
    Degree_v::iterator it=res.begin();
    for (;ita!=itaend;++it,++itb,++ita)
        *it = (*ita)-(*itb);
    return res;
}

Index operator * (const Index & a, int fois) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end();
    Index res(itaend-ita);
    Degree_v::iterator it=res.begin();
    for (;ita!=itaend;++it,++ita)
        *it = (*ita)*fois;
    return res;
}

Index operator / (const Index & a, int divisepar) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end();
    Index res(itaend-ita);
    Degree_v::iterator it=res.begin();
    for (;ita!=itaend;++it,++ita)
        *it = (*ita)/divisepar;
    return res;
}

bool operator != (const Index & i1, const Index & i2) {
    return !(i1==i2);
}

// >= and <= are *partial* ordering on Degree_v
// they return TRUE if and only if >= or <= is true for *all* coordinates
bool operator >= (const Index & a, const Index & b) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end();
    Degree_v::const_iterator itb=b.begin();
#ifdef CASPP_DEBUG_SUPPORT
    if (itaend-ita!=signed(b.size()))
        setsizeerr(gettext("index.cc Index operator >="));
#endif
    for (;ita!=itaend;++ita,++itb) {
        if ((*ita)<(*itb))
            return false;
    }
    return true;
}

bool operator <= (const Index & a, const Index & b) {
    Degree_v::const_iterator ita=a.begin(),itaend=a.end();
    Degree_v::const_iterator itb=b.begin();
#ifdef CASPP_DEBUG_SUPPORT
    if (itaend-ita!=signed(b.size()))
        setsizeerr(gettext("index.cc Index operator >="));
#endif
    for (;ita!=itaend;++ita,++itb) {
        if ((*ita)>(*itb))
            return false;
    }
    return true;
}


int sum_degree(const Index & v1) {
    int i=0;
    for (Degree_v::const_iterator it=v1.begin();it!=v1.end();++it)
        i=i+(*it);
    return(i);
}

bool i_lex_is_greater(const Index & v1, const Index & v2) {
    Degree_v::const_iterator it1=v1.begin();
    Degree_v::const_iterator it2=v2.begin();
    Degree_v::const_iterator it1end=v1.end();
#ifdef CASPP_DEBUG_SUPPORT
    if (it1end-it1!=signed(v2.size()))
        setsizeerr(gettext("index.cc Index i_lex_is_greater"));
#endif
    for (;it1!=it1end;++it1) {
        if ( (*it1)!=(*it2) ) {
            if  ( (*it1)>(*it2))
                return(true);
            else
                return(false);
        }
        ++it2;
    }
    return(true);
}

bool lex_is_strictly_greater_Degree(const Degree_v & v1, const Degree_v & v2) {
    assert(v1.size()==v2.size());
    Degree_v::const_iterator it1=v1.begin(),it1end=v1.end();
    Degree_v::const_iterator it2=v2.begin();
    for (;it1!=it1end;++it2,++it1) {
        if ( (*it1)!=(*it2) ) {
            if  ( (*it1)>(*it2))
                return true;
            else
                return false;
        }
    }
    return false;
}

bool i_lex_is_strictly_greater(const Index & v1, const Index & v2) {
    Degree_v::const_iterator it1=v1.begin();
    Degree_v::const_iterator it2=v2.begin();
    Degree_v::const_iterator it1end=v1.end();
#ifdef CASPP_DEBUG_SUPPORT
    if (it1end-it1!=signed(v2.size()))
        setsizeerr(gettext("index.cc Index i_lex_is_greater"));
#endif
    for (;it1!=it1end;++it1) {
        if ( (*it1)!=(*it2) ) {
            if  ( (*it1)>(*it2))
                return(true);
            else
                return(false);
        }
        ++it2;
    }
    return(false);
}

/*
  bool i_revlex_is_greater(const Index & v1, const Index & v2) {
    return revlex_is_greater(*v1._p,*v2._p);
  }
  */

bool i_total_lex_is_greater(const Index & v1, const Index & v2) {
    int d1=sum_degree(v1);
    int d2=sum_degree(v2);
    if (d1!=d2) {
        if (d1>d2)
            return(true);
        else
            return(false);
    }
    return(i_lex_is_greater(v1,v2));
}

bool i_total_lex_is_strictly_greater(const Index & v1, const Index & v2) {
    return !i_total_lex_is_greater(v2,v1);
}

bool i_total_revlex_is_greater(const Index & v1, const Index & v2) {
    int d1=sum_degree(v1);
    int d2=sum_degree(v2);
    if (d1!=d2) {
        if (d1>d2)
            return(true);
        else
            return(false);
    }
    // find order with variables reversed then reverse order
    // return !i_lex_is_strictly_greater(v1,v2);
    Degree_v::const_iterator it1=v1.end()-1;
    Degree_v::const_iterator it2=v2.end()-1;
    Degree_v::const_iterator it1end=v1.begin()-1;
#ifdef CASPP_DEBUG_SUPPORT
    if (it1-it1end!=signed(v2.size()))
        setsizeerr(gettext("index.cc Index i_total_revlex_is_greater"));
#endif
    for (;it1!=it1end;--it1) {
        if ( *it1 != *it2 )
            return *it1<*it2;
        --it2;
    }
    return true;
}

// revlex on 1st 3 vars, then revlex on remaining vars
bool i_3var_is_greater(const Index & v1, const Index & v2) {
    Degree_v::const_iterator it1=v1.begin();
    Degree_v::const_iterator it2=v2.begin();
    int d1=*it1+*(it1+1)+*(it1+2);
    int d2=*it2+*(it2+1)+*(it2+2);
    if (d1!=d2)
        return d1>=d2;
    if (*(it1+2)!=*(it2+2))
        return *(it1+2)<=*(it2+2);
    if (*(it1+1)!=*(it2+1))
        return *(it1+1)<=*(it2+1);
    if (*it1!=*it2) v1.dbgprint(); // instantiate
    d1=sum_degree(v1);
    d2=sum_degree(v2);
    if (d1!=d2)
        return d1>=d2;
    Degree_v::const_iterator it1end=it1+2;
    it1 = v1.end()-1;
    it2 = v2.end()-1;
    for (;it1!=it1end;--it1,--it2) {
        if (*it1!=*it2)
            return *it1<=*it2;
    }
    return true;
}

// revlex on 1st 7 vars, then revlex on remaining vars
bool i_7var_is_greater(const Index & v1, const Index & v2) {
    Degree_v::const_iterator it1=v1.begin();
    Degree_v::const_iterator it2=v2.begin();
    int d1=*it1+*(it1+1)+*(it1+2)+*(it1+3)+*(it1+4)+*(it1+5)+*(it1+6);
    int d2=*it2+*(it2+1)+*(it2+2)+*(it2+3)+*(it2+4)+*(it2+5)+*(it2+6);
    if (d1!=d2)
        return d1>=d2;
    if (*(it1+6)!=*(it2+6))
        return *(it1+6)<=*(it2+6);
    if (*(it1+5)!=*(it2+5))
        return *(it1+5)<=*(it2+5);
    if (*(it1+4)!=*(it2+4))
        return *(it1+4)<=*(it2+4);
    if (*(it1+3)!=*(it2+3))
        return *(it1+3)<=*(it2+3);
    if (*(it1+2)!=*(it2+2))
        return *(it1+2)<=*(it2+2);
    if (*(it1+1)!=*(it2+1))
        return *(it1+1)<=*(it2+1);
    d1=sum_degree(v1);
    d2=sum_degree(v2);
    if (d1!=d2)
        return d1>=d2;
    Degree_v::const_iterator it1end=it1+6;
    it1 = v1.end()-1;
    it2 = v2.end()-1;
    for (;it1!=it1end;--it1,--it2) {
        if (*it1!=*it2)
            return *it1<=*it2;
    }
    return true;
}

// revlex on 1st 11 vars, then revlex on remaining vars
bool i_11var_is_greater(const Index & v1, const Index & v2) {
    Degree_v::const_iterator it1=v1.begin();
    Degree_v::const_iterator it2=v2.begin();
    int d1=*it1+*(it1+1)+*(it1+2)+
            *(it1+3)+*(it1+4)+*(it1+5)+*(it1+6)+
            *(it1+7)+*(it1+8)+*(it1+9)+*(it1+10);
    int d2=*it2+*(it2+1)+*(it2+2)+
            *(it2+3)+*(it2+4)+*(it2+5)+*(it2+6)+
            *(it2+7)+*(it2+8)+*(it2+9)+*(it2+10);
    if (d1!=d2)
        return d1>=d2;
    if (*(it1+10)!=*(it2+10))
        return *(it1+10)<=*(it2+10);
    if (*(it1+9)!=*(it2+9))
        return *(it1+9)<=*(it2+9);
    if (*(it1+8)!=*(it2+8))
        return *(it1+8)<=*(it2+8);
    if (*(it1+7)!=*(it2+7))
        return *(it1+7)<=*(it2+7);
    if (*(it1+6)!=*(it2+6))
        return *(it1+6)<=*(it2+6);
    if (*(it1+5)!=*(it2+5))
        return *(it1+5)<=*(it2+5);
    if (*(it1+4)!=*(it2+4))
        return *(it1+4)<=*(it2+4);
    if (*(it1+3)!=*(it2+3))
        return *(it1+3)<=*(it2+3);
    if (*(it1+2)!=*(it2+2))
        return *(it1+2)<=*(it2+2);
    if (*(it1+1)!=*(it2+1))
        return *(it1+1)<=*(it2+1);
    d1=sum_degree(v1);
    d2=sum_degree(v2);
    if (d1!=d2)
        return d1>=d2;
    Degree_v::const_iterator it1end=it1+10;
    it1 = v1.end()-1;
    it2 = v2.end()-1;
    for (;it1!=it1end;--it1,--it2) {
        if (*it1!=*it2)
            return *it1<=*it2;
    }
    return true;
}

bool i_total_revlex_is_strictly_greater(const Index & v1, const Index & v2) {
    return !i_total_revlex_is_greater(v2,v1);
}

bool disjoint(const Index & a,const Index & b) {
    Degree_v::const_iterator it=a.begin(),itend=a.end(),jt=b.begin();
    for (;it!=itend;++jt,++it) {
        if (*it && *jt)
            return false;
    }
    return true;
}

CASPP_NS_END
